COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	collap[w88,jmc]		Collapsible circumscription, re Kolaitis talk
C00004 ENDMK
C⊗;
collap[w88,jmc]		Collapsible circumscription, re Kolaitis talk

	Here are two directions in which the results (Lifschitz
and Kolaitis + Papadimitriou) might be extended.

	1. In the non-logic programming case, it might be that
when a circumscription is collapsible to a first order formula,
there will be a number $k$ such that any model is elementarily
equivalent to a model with $k$ or fewer elements.

	VAL points out that this is not right.  Kolaitis's point was that
the circumscription is collapsible in the Horn clause case when it
corresponds to a finite expansion of the original clauses.

	2. A circumscription may be collapsible relative to a given
predicate or function where this predicate or function is not itself
axiomatizable.  For example, it may be collapsible relative to a
predicate picking out natural numbers or Lisp S-expressions from
some larger domain.